package _4lists.src.cycleLinked;


/**
 * @className: zhaohuan
 * @description:
 * @author: myself
 * @date: 2025/7/22 23:03
 * @version: 0.1
 * @since: JDK17
 */

public class zhaohuan {
    static class Node{//创建出来的相关节点
        private int val;
        private Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }

        public Node() {
        }

        public Node(int val) {
            this.val = val;
        }
    }

    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {//判断初始head情况
            return null;
        }
        //提前进行走，为后续两者相遇打铺垫
        Node n1 = head.next;//慢指针
        Node n2 = head.next.next;//快指针
        while (n1 != n2) {//相遇时停止
            if (n2.next == null || n2.next.next == null) {
                return null;//此时代表无环
            }
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = head;//使快指针回到起来
        while (n1 != n2) {//当两者相遇时，即是相关所求环的头节点
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;//n1和n2都可以
    }
}
